#include "solver.h"

namespace fcsp {
  using namespace std;

  bool Solver::FuzzyAC2001(FCSP *csp, bool partial) {
    pair<bool, bool> res(false, false);
    set<Variable*, VarPtrComp> queue;

    supports_.clear();

    list<Variable>::iterator it = csp->variables().begin();
    for (; it != csp->variables().end(); ++it) {
      queue.insert(&(*it));
    }

    Variable *variable,
      *var_adjacent;
    set<Variable*>::iterator var_adj_it;
    while (!res.first && !queue.empty()) {
      variable = (*queue.begin());
      queue.erase(queue.begin());
      for(var_adj_it = variable->adjacents().begin();
          var_adj_it != variable->adjacents().end(); ++var_adj_it) {
        var_adjacent = (*var_adj_it);
        if (FindSupports(var_adjacent, variable, csp, partial)) {
          queue.insert(var_adjacent);
        }

        res = PruneVar(var_adjacent);
        if (res.second) {
          queue.insert(var_adjacent);
        }
      }
    }
    return !res.first;
  }

  pair<bool, bool> Solver::PruneVar(Variable *x) {
    bool no_solution = false;
    bool change = false;
    map<int , double>::const_iterator it = x->preferences().begin();
    while (it != x->preferences().end()) {
      if (FCSP::IsLowerPref((*it).second)) {        
        int x_value = (*it).first;
        ++it;
        x->RemoveValue(x_value);
        change = true;
      } else {
        ++it;
      }
    }
    no_solution = x->preferences().empty();

    return pair<bool, bool>(no_solution, change);
  }

  bool Solver::FindSupports(Variable *x, Variable *y, FCSP *csp, bool partial) {
    map<int , double>::const_iterator it1 = x->preferences().begin(),
      it2;
    Support support,
      inv_support;
    int x_value,
      y_value;
    double x_pref;
    bool change = false;
    pair<BinaryConstraint&, bool> constraint = csp->GetConstraint(*x, *y);

    if (constraint.second) {
      for (; it1 != x->preferences().end(); ++it1) {
        x_value = (*it1).first;
        support = GetSupport(x->id(), x_value, y->id());

        if (!support.valid || y->preferences().count(support.value) <= 0) {
          support = GetMaxPrefSupport(constraint.first, x_value);

          x_pref = x->GetPreference(x_value);
          if (x_pref > support.pref) {
            x->SetPreference(x_value, support.pref);
            x_pref = support.pref;
          } else {
            support.pref = x_pref;
          }
          support.valid = true;
          supports_[x->id()][x_value][y->id()] = support;

          for (it2 = y->preferences().begin(); !partial && it2 != y->preferences().end(); ++it2) {
            y_value = (*it2).first;

            if (constraint.first.GetPreference(x_value, y_value) > x_pref) {
              csp->SetConstraintPref(*x, *y, x_value, y_value, x_pref);

              inv_support = GetSupport(y->id(), support.value, x->id());
              if (inv_support.value == x_value && inv_support.pref > x_pref) {
                inv_support.valid = false;
                supports_[y->id()][support.value][x->id()] = inv_support;

                change = true;
              }
            }
          }
        }
      }
    }
    return change;
  }

  Solver::Support Solver::GetSupport(int x_id, int x_value, int y_id) {
    Support support;
    map< int, map< int, map<int, Support> > >::iterator it1;
    it1 = supports_.find(x_id);
    if (it1 != supports_.end()) {
      map< int, map<int, Support> >::iterator it2;
      it2 = (*it1).second.find(x_value);
      if (it2 != (*it1).second.end()) {
         map<int, Support>::iterator it3;
         it3 = (*it2).second.find(y_id);
         if(it3 != (*it2).second.end()) {
           support = supports_[x_id][x_value][y_id];
         }
      }
    }
    return support;
  }

  Solver::Support Solver::GetMaxPrefSupport(BinaryConstraint &constraint, int value_x) {
    Support support;
    pair<map<int, double> &, bool> prefs = constraint.GetPreferences(value_x);
    if (prefs.second) {
      map<int, double>::iterator it = prefs.first.begin();
      for (; it != prefs.first.end(); ++it) {
        if ((*it).second > support.pref) {
          support.pref = (*it).second;
          support.value = (*it).first;
          support.valid = true;
        }
      }
    }
    return support;
  }
}
